{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Partition Array Such That Maximum Difference Is K"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: partitionArray"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #划分数组使最大差为 K"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组 <code>nums</code> 和一个整数 <code>k</code> 。你可以将 <code>nums</code> 划分成一个或多个 <strong>子序列</strong> ，使 <code>nums</code> 中的每个元素都 <strong>恰好</strong> 出现在一个子序列中。</p>\n",
    "\n",
    "<p>在满足每个子序列中最大值和最小值之间的差值最多为 <code>k</code> 的前提下，返回需要划分的 <strong>最少</strong> 子序列数目。</p>\n",
    "\n",
    "<p><strong>子序列</strong> 本质是一个序列，可以通过删除另一个序列中的某些元素（或者不删除）但不改变剩下元素的顺序得到。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [3,6,1,2,5], k = 2\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>\n",
    "可以将 nums 划分为两个子序列 [3,1,2] 和 [6,5] 。\n",
    "第一个子序列中最大值和最小值的差值是 3 - 1 = 2 。\n",
    "第二个子序列中最大值和最小值的差值是 6 - 5 = 1 。\n",
    "由于创建了两个子序列，返回 2 。可以证明需要划分的最少子序列数目就是 2 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,2,3], k = 1\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>\n",
    "可以将 nums 划分为两个子序列 [1,2] 和 [3] 。\n",
    "第一个子序列中最大值和最小值的差值是 2 - 1 = 1 。\n",
    "第二个子序列中最大值和最小值的差值是 3 - 3 = 0 。\n",
    "由于创建了两个子序列，返回 2 。注意，另一种最优解法是将 nums 划分成子序列 [1] 和 [2,3] 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [2,2,4,5], k = 0\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>\n",
    "可以将 nums 划分为三个子序列 [2,2]、[4] 和 [5] 。\n",
    "第一个子序列中最大值和最小值的差值是 2 - 2 = 0 。\n",
    "第二个子序列中最大值和最小值的差值是 4 - 4 = 0 。\n",
    "第三个子序列中最大值和最小值的差值是 5 - 5 = 0 。\n",
    "由于创建了三个子序列，返回 3 。可以证明需要划分的最少子序列数目就是 3 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 &lt;= nums[i] &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 &lt;= k &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [partition-array-such-that-maximum-difference-is-k](https://leetcode.cn/problems/partition-array-such-that-maximum-difference-is-k/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [partition-array-such-that-maximum-difference-is-k](https://leetcode.cn/problems/partition-array-such-that-maximum-difference-is-k/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,6,1,2,5]\\n2', '[1,2,3]\\n1', '[2,2,4,5]\\n0']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionArray(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        ans = i = 0\n",
    "        while i < n:\n",
    "            j = i\n",
    "            while j+1 < n and nums[j+1] - nums[i] <= k:\n",
    "                j += 1\n",
    "            ans += 1\n",
    "            i = j+1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionArray(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        result = 1\n",
    "        last = nums[0]\n",
    "        for num in nums:\n",
    "            if num - last > k:\n",
    "                last = num\n",
    "                result += 1\n",
    "        return result\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "        \n",
    "\n",
    "           \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionArray(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        cur = 0\n",
    "        n = len(nums)\n",
    "        while cur < n:\n",
    "            cur = bisect_right(nums, nums[cur] + k)\n",
    "            ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionArray(self, nums: List[int], k: int, res = 0, cur = -123456) -> int:\n",
    "        for x in sorted(nums):\n",
    "            if x - cur > k: cur, res = x, res + 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionArray(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        res = 1\n",
    "        pre_val = nums[0]\n",
    "        for val in nums:\n",
    "            if val-pre_val>k:\n",
    "                res += 1\n",
    "                pre_val = val \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionArray(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        l = 0\n",
    "        r = 0\n",
    "        while l < n:\n",
    "            while r < n and nums[r] - nums[l] <= k:\n",
    "                r += 1\n",
    "            ans += 1\n",
    "            l = r\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionArray(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        result = 1\n",
    "        last = nums[0]\n",
    "        for num in nums:\n",
    "            if num - last > k:\n",
    "                last = num\n",
    "                result += 1\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionArray(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        start = nums[0]\n",
    "        ans = 0\n",
    "        for num in nums[1:]:\n",
    "            if num - start > k:\n",
    "                start = num\n",
    "                ans += 1\n",
    "        return ans+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionArray(self, nums: list[int], k: int) -> int:\n",
    "        def test(target):\n",
    "            tot=0\n",
    "            p=0\n",
    "            while p<len(nums):\n",
    "                left=0\n",
    "                right = len(nums)-1\n",
    "                while left<right:\n",
    "                    mid = (left+right)//2+1\n",
    "                    if nums[mid]-nums[p]>k:\n",
    "                        right=mid-1\n",
    "                    else:\n",
    "                        left=mid\n",
    "                p=left+1\n",
    "                tot+=1\n",
    "            return tot<=target\n",
    "        nums.sort()\n",
    "        left=1\n",
    "        right=len(nums)\n",
    "        while left<right:\n",
    "            mid = (left+right)//2\n",
    "            if test(mid):\n",
    "                right=mid\n",
    "            else:\n",
    "                left=mid+1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionArray(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        cnt = 1\n",
    "        min_num = nums[0]\n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i] - min_num > k:\n",
    "                cnt += 1\n",
    "                min_num = nums[i]\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionArray(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        result = 1\n",
    "        last = nums[0]\n",
    "        for num in nums:\n",
    "            if num - last > k:\n",
    "                last = num\n",
    "                result += 1\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionArray(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        res = nums[0]\n",
    "        for i in range(1,n):\n",
    "            if nums[i] - res <= k:\n",
    "                continue\n",
    "            else:\n",
    "                res = nums[i]\n",
    "                ans += 1\n",
    "        return ans + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionArray(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        result = 0\n",
    "        left, right = 0, 0\n",
    "        result = 1\n",
    "        while(right < len(nums)):\n",
    "            if(nums[right] - nums[left] > k):\n",
    "                left = right      \n",
    "                result += 1 \n",
    "            right += 1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionArray(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        l = float('-inf')\n",
    "        result = 0\n",
    "        for n in nums:\n",
    "            if n - l > k:\n",
    "                l = n\n",
    "                result += 1\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionArray(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort();ans,x=1,nums[0]\n",
    "        for i in nums:\n",
    "            if(i-x<=k):continue\n",
    "            else:ans,x=ans+1,i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionArray(self, nums: List[int], k: int) -> int:\n",
    "        # 先排序\n",
    "        nums.sort()\n",
    "        count = len(nums)\n",
    "\n",
    "        _min = nums[0]\n",
    "        result = 1\n",
    "        for i in range(1, count):\n",
    "            if nums[i] - _min > k:\n",
    "                result += 1\n",
    "                _min = nums[i]\n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionArray(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        ans = 1\n",
    "        pre =nums[0]\n",
    "        for num in nums[1:]:\n",
    "            if num <= pre+k:\n",
    "                continue\n",
    "            else:\n",
    "                ans += 1\n",
    "                pre = num\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionArray(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        n=len(nums)\n",
    "        ans=1\n",
    "        i=nums[0]\n",
    "        for j in range(n):\n",
    "            if nums[j]-i>k:\n",
    "                i=nums[j]\n",
    "                ans+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionArray(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        result = 1\n",
    "        last = nums[0]\n",
    "        for num in nums:\n",
    "            if num - last > k:\n",
    "                last = num\n",
    "                result += 1\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionArray(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        ans = 1\n",
    "        t = nums[0]\n",
    "        for i in range(1, n):\n",
    "            if nums[i] - t > k:\n",
    "                t = nums[i]\n",
    "                ans += 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionArray(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "\n",
    "        cnt=1\n",
    "        l=nums[0]\n",
    "        r=nums[0]+k\n",
    "        \n",
    "        for i,v in enumerate(nums):\n",
    "            if v >r:\n",
    "                l=v\n",
    "                r=v+k\n",
    "                cnt+=1\n",
    "        \n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionArray(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        ans = 1\n",
    "        pre = nums[0]\n",
    "        for x in nums[1:]:\n",
    "            if x - pre > k:\n",
    "                ans += 1\n",
    "                pre = x\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionArray(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        m = nums[0]\n",
    "        ret = 1\n",
    "        for x in nums[1:]:\n",
    "            if x - m > k:\n",
    "                ret += 1\n",
    "                m = x\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionArray(self, nums: List[int], k: int) -> int:\n",
    "        r = 1\n",
    "        nums = sorted(nums)\n",
    "        \n",
    "        if len(nums) == 1:\n",
    "            return 1\n",
    "        cur_big = nums[0]\n",
    "        cur_sml = nums[0]\n",
    "        for n in nums:\n",
    "            print(n)\n",
    "            cur_big = max(cur_big, n)\n",
    "            cur_sml = min(cur_sml, n)\n",
    "            if cur_big - cur_sml > k:\n",
    "                r += 1\n",
    "                cur_big = n\n",
    "                cur_sml = n\n",
    "        return r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionArray(self, nums: List[int], k: int) -> int:\n",
    "        ans=0\n",
    "        nums.sort()\n",
    "        p=-inf \n",
    "        for x in nums:\n",
    "            if x-p>k:\n",
    "                ans+=1\n",
    "                p=x\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionArray(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        nums.sort()\n",
    "        start = True\n",
    "        cur_min = nums[0]\n",
    "        res = 1\n",
    "        for num in nums[1:]:\n",
    "            if num>cur_min+k:\n",
    "                res+=1\n",
    "                cur_min = num\n",
    "        return res\n",
    "            \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionArray(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        res = 1\n",
    "        tgt = nums[0]\n",
    "        for n in nums:\n",
    "            if n - tgt > k:\n",
    "                res += 1\n",
    "                tgt = n\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionArray(self, nums: list[int], k: int) -> int:\n",
    "        def test():\n",
    "            tot=0\n",
    "            p=0\n",
    "            while p<len(nums):\n",
    "                left=0\n",
    "                right = len(nums)-1\n",
    "                while left<right:\n",
    "                    mid = (left+right)//2+1\n",
    "                    if nums[mid]-nums[p]>k:\n",
    "                        right=mid-1\n",
    "                    else:\n",
    "                        left=mid\n",
    "                p=left+1\n",
    "                tot+=1\n",
    "            return tot\n",
    "        nums.sort()\n",
    "        return test()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionArray(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        pre = nums[0]\n",
    "        ans = 0\n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i] - pre > k:\n",
    "                ans += 1\n",
    "                pre = nums[i]\n",
    "        return ans + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionArray(self, nums: list[int], k: int) -> int:\n",
    "        def test(target):\n",
    "            list1 = nums.copy()\n",
    "            tot=0\n",
    "            p=0\n",
    "            while p<len(list1):\n",
    "                left=0\n",
    "                right = len(list1)-1\n",
    "                while left<right:\n",
    "                    mid = (left+right)//2+1\n",
    "                    if list1[mid]-list1[p]>k:\n",
    "                        right=mid-1\n",
    "                    else:\n",
    "                        left=mid\n",
    "                p=left+1\n",
    "                tot+=1\n",
    "            return tot<=target\n",
    "        nums.sort()\n",
    "        left=1\n",
    "        right=len(nums)\n",
    "        while left<right:\n",
    "            mid = (left+right)//2\n",
    "            if test(mid):\n",
    "                right=mid\n",
    "            else:\n",
    "                left=mid+1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionArray(self, nums: List[int], k: int) -> int:\n",
    "        # 先排序\n",
    "        nums.sort()\n",
    "        count = len(nums)\n",
    "\n",
    "        _min = nums[0]\n",
    "        _num = _min + k\n",
    "        result = 1\n",
    "        for i in range(1, count):\n",
    "            if nums[i] > _num:\n",
    "                result += 1\n",
    "                _min = nums[i]\n",
    "                _num = _min + k\n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionArray(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        result = 0\n",
    "        left, right = 0, 0\n",
    "        result = 1\n",
    "        while(right < len(nums)):\n",
    "            if(nums[right] - nums[left] > k):\n",
    "                left = right      \n",
    "                result += 1 \n",
    "            right += 1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionArray(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        partitions = 1\n",
    "        min_val = nums[0]\n",
    "        max_val = nums[0]\n",
    "\n",
    "        for num in nums:\n",
    "            if num - min_val > k or max_val - num > k:\n",
    "                partitions += 1\n",
    "                min_val = num\n",
    "                max_val = num\n",
    "            else:\n",
    "                max_val = max(max_val, num)\n",
    "\n",
    "        return partitions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionArray(self, nums: List[int], k: int) -> int:\n",
    "        c = list(set(nums))\n",
    "        c.sort()\n",
    "        n = len(c)\n",
    "        result = 0\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            min_value = c[i]\n",
    "            j = i + 1\n",
    "            while j < n and c[j] - c[i] <= k:\n",
    "                j += 1\n",
    "            result += 1\n",
    "            i = j\n",
    "        return result"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
